package main

import (
	"fmt"
	"sort"
)

/*
	摆动排序 II
给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
你可以假设所有输入数组都可以得到满足题目要求的结果。

示例 1：
输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

示例 2：
输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]
 */

func wiggleSort(nums []int) {
	length := len(nums)
	// 以 1, 3, 2, 2, 3, 1为例
	j, k := length, (length + 1)>>1   //  6  3
	t := make([]int, length)
	copy(t, nums)
	sort.Ints(t)   //  先排序    1 1 2 2 3 3
	for i := 0; i < length; i++ {
		if i&1 == 1 {
			j--
			nums[i] = t[j]
		} else {
			k--
			nums[i] = t[k]
		}
	}
	fmt.Println(nums)
}

func wiggleSort1(nums []int) {
	/*
		思路  先排序 在二分排序
	*/
	// 快速排序
	length := len(nums)
	quickSort(nums, 0, length-1)
	fmt.Println(nums)
	if length <= 2 {
		return
	} else if length == 3 {
		nums[1], nums[2] = nums[2], nums[1]
		return
	}
	left, right := 1, length-2
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left += 2
		right -= 2
	}
	fmt.Println(nums)
}

func quickSort(nums []int, left, right int) {
	if left >= right {
		return
	}
	val := nums[left]
	k := left
	for i := left + 1; i <= right; i++ {
		if nums[i] < val { // 比val小
			nums[k] = nums[i]
			nums[i] = nums[k+1]
			k++
		}
	}
	nums[k] = val
	quickSort(nums, left, k-1)
	quickSort(nums, k+1, right)
}

func main() {
	wiggleSort([]int{1, 3, 2, 2, 3, 1})
}
